18.212 Spring 2020
Algebraic Combinatorics

Lectures: Monday and Wednesday 9:30-11, room 4-153

Instructor: Thomas Lam, room 2-169, tfylam@mit.edu

Office hours: Monday and Wednesday, 1-2pm

Course description: We will discuss applications of algebra to combinatorics and vice versa. Topics may include: graph eigenvalues, random walks, domino tilings, matrix tree theorem, electrical networks, Eulerian tours, permutations, partitions, Young diagrams, Young tableaux, Sperner's theorem, Gaussian coefficients, RSK correspondence, partially ordered sets, ...
Level: advanced undergraduate

Grading: Based on several problem sets. There will be no exams.

Going online: Beginning March 12,

• All problem sets are to be submitted via email.
  
• Next lecture is March 30.
  
• All office hours are cancelled.
  
• Students in the class should have received an invitation to join a class workspace (message board) on Slack.

Recordings:

• March 30 Young diagrams and Gaussian coefficients [AC, Chapter 6]
• April 1(Sorry for the technical problems in this lecture!) L(m,n) is Sperner [AC, Chapter 6]
• April 6 Euler's pentagonal number theorem
• April 8 Tableaux and Hook-length formula [AC, Chapter 8]
• April 13Proof of Hook-length formula
• April 15Frobenius formula and Robinson-Schensted Algorithm [AC, Chapter 8]
• April 22Growth diagram approach to RSK [EC2, Chapter 7]
• April 27Schur functions and plane partitions [AC, Chapter 8]
• April 29Matrix Tree theorem [AC, Chapter 9]
• May 4Matrix Tree theorem [AC, Chapter 9
• May 6Electrical networks
• May 11Groves and response matrices

Problem sets: There will be problem sets every two weeks. Homework solutions must be typed in LaTeX and either submitted at the beginning of class, or emailed to me before midnight (i.e. by 11:59pm) of the due date. Late homework grades are penalized 20% per late day.
At the front of your homework solution, please acknowledge any books, online sources, etc. consulted, and indicate other students you worked with on the homework.

References:
The course will have significant overlap with the following optional textbook:
[AC]  Algebraic Combinatorics: Walks, Trees, Tableaux, and More by R. P. Stanley, Springer, 2nd ed, 2018. Version of 2013 is available as pdf file

Additional reading:

[EC1]   [EC2]  Enumerative Combinatorics, Vol 1 and Vol 2, by R. P. Stanley, Cambridge University Press, 2011 and 2001. Volume 1 is available as pdf file

[vL-W]  A Course in Combinatorics by J. H. van Lint and R. M. Wilson, Cambridge University Press, 2001.

List of lectures:

• February 3: Graph eigenvalues I ([AC, Chapter 1])
  
• February 5: Graph eigenvalues II
  
• February 10: Walks in cubes ([AC, Chapter 2])
  
• February 12: Random walks, stationary distribution ([AC, Chapter 3])
  
• February 18 (MIT Monday): Hitting times
  
• February 19: Counting domino tilings
  
• February 24: Domino tilings of rectangles
  
• February 26: Partially ordered sets
  
• March 2: Sperner's Theorem I
  
• March 4: Sperner's Theorem II
  
• March 9: Group actions on boolean algebras I
  
• March 11: Group actions on boolean algebras II
  
• March 16: No lecture (switching to online)
  
• March 18: No lecture (switching to online)
  
• March 23: No lecture (SPRING BREAK)
  
• March 25: No lecture (SPRING BREAK)